package com.vincent.algorithms.sort;

import java.util.ArrayList;
import java.util.Collections;

/**
 * 桶排序: 计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定 三大线性排序
 * 假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排)
 *
 * 分析：桶排序最好情况下使用线性时间O(n)，桶排序的时间复杂度，取决与对各个桶之间数据进行排序的时间复杂度，
 * 因为其它部分的时间复杂度都为O(n)。很显然，桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少。但相应的空间消耗就会增大
 *
 *  1.找出待排序数组中的最大值max、最小值min
 *  2.我们使用 动态数组ArrayList 作为桶，桶里放的元素也用 ArrayList 存储。桶的数量为(max-min)/arr.length+1
 *  3.遍历数组 arr，计算每个元素 arr[i] 放的桶
 *  4.每个桶各自排序
 *  5.遍历桶数组，把排序好的元素放进输出数组
 *
 * 使用情况：桶排序可用于最大最小值相差较大的数据情况，比如[9012,19702,39867,68957,83556,102456]。
 * 但桶排序要求数据的分布必须均匀，否则可能导致数据都集中到一个桶中。比如[104,150,123,132,20000], 这种数据会导致前4个数都集中到同一个桶中。导致桶排序失效。
 *
 * 对于N个待排数据，M个桶，平均每个桶[N/M]个数据的桶排序平均时间复杂度为：
 * O(N)+O(M*(N/M)*log(N/M))=O(N+N*(logN-logM))=O(N+N*logN-N*logM)
 * 当N=M时，即极限情况下每个桶只有一个数据时。桶排序的最好效率能够达到O(N)。
 * 总结：桶排序的平均时间复杂度为线性的O(N+C)，其中C=N*(logN-logM)。如果相对于同样的N，桶数量M越大，其效率越高，
 * 最好的时间复杂度达到O(N)。当然桶排序的空间复杂度为O(N+M)，如果输入数据非常庞大，而桶的数量也非常多，则空间代价无疑是昂贵的
 *
 * Created by yangwenchang on 2017/8/25.
 */
public class BucketSort {

    public static void sort(int[] arr){
        int min = arr[0];
        int max = arr[0];

        for (int i=0;i<arr.length;i++){
            min = Math.min(min,arr[i]);
            max = Math.max(max,arr[i]);
        }

        int bucketNum = (max-min)/arr.length + 1;
        ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
        System.out.println("桶数："+bucketNum+"-"+min+"-"+max);
        for(int i = 0; i < bucketNum; i++){
            bucketArr.add(new ArrayList<Integer>());
        }

        //将每个元素放入桶
        for(int i = 0; i < arr.length; i++){
            int num = (arr[i] - min) / (arr.length);
            bucketArr.get(num).add(arr[i]);
        }

        //对每个桶进行排序  这里可自行使用各种算法桶排序
        for(int i = 0; i < bucketArr.size(); i++){
            Collections.sort(bucketArr.get(i));
            System.out.println("桶-"+i+bucketArr.get(i).toString());
        }

        //把各个桶的元素拼接起来就是有序的
        System.out.println(bucketArr.toString());

    }

    public static void main(String[] args) {
        int[] arr = {3,4,13,25,5,23,29};

        sort(arr);

    }


}
